Modern processors support virtual memory capability. A virtual memory system maps, or translates, virtual addresses used by a program to physical addresses used by hardware to address memory. Virtual memory has the advantages of hiding the fragmentation of physical memory from the program, facilitating program relocation, and of allowing the program to see a larger memory address space than the actual physical memory available to it. These advantages are particularly beneficial in modern systems that support time-sharing of the processor by multiple programs or processes.
The operating system creates and maintains in memory translation tables, often referred to as page tables in a paged virtual memory system, that map virtual addresses to physical addresses. The translation tables may be in the form of a hierarchy of tables, some of which map virtual addresses to intermediate table addresses. When a program accesses memory using a virtual address, the translation tables must be accessed to accomplish the translation of the virtual address to its physical address, commonly referred to as a page table walk, or table walk. The additional memory accesses to access the translation tables can significantly delay the ultimate access to the memory to obtain the data or instruction desired by the program.
Modern processors include translation-lookaside buffers (TLB) to address this problem and improve performance. A TLB is a hardware structure of a processor that caches the virtual to physical address translations in order to greatly reduce the likelihood that the translation tables will need to be accessed. The virtual address to be translated is looked up in the TLB and the TLB provides the physical address, if the virtual address hits in the TLB, in much less time than would be required to access the translation tables in memory to perform the table walk. The efficiency (hit rate) of TLBs is crucial to processor performance.
Each process, or context, has its own unique address space and associated address translations. Therefore, the TLB entries for one process might be incorrect for another process. That is, the TLB entries created for one process might be stale with respect to another process. One phenomenon that can reduce TLB efficiency is when the processor switches from running one process to running a different process. The system must ensure that it does not use stale TLB entries to incorrectly translate virtual addresses of the new process by using address translations cached in the TLB for the old process.